/**
 * Created with IntelliJ IDEA.
 * Description:
 * Date: 2025-04-09
 * Time: 22:28
 */
public class Main {
    public int waysToStep(int n){
        //1.创建 dp 表
        //2.初始化
        //3.填表
        //4.返回值

        int MOD = (int)1e9 + 7;

        //处理一下边界情况
        if (n == 1 || n == 2){
            return n;
        }
        if (n == 3){
            return 4;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1; dp[2] = 2;dp[3] = 4;
        for (int i = 4; i <= n; i++) {
            dp[i] = ((dp[i-1] +dp[i-2]) % MOD +dp[i-3]) % MOD;
        }
        return dp[n];
    }
}
